/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
 * This file is part of Suneido - The Integrated Application Platform
 * see: http://www.suneido.com for more information.
 * 
 * Copyright (c) 2000 Suneido Software Corp. 
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation - version 2. 
 *
 * This program is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE.  See the GNU General Public License in the file COPYING
 * for more details. 
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*
bitmapped garbage collecting memory manager

- mark/sweep
- conservative - blocks are not moved or modified
- handles internal pointers (not just to start of blocks)
- bitmap used to store block starts
	- used to determine block extent from arbitrary address
- bitmap for marks
- free lists
	- rebuilt by sweep
	- segregated by size
	- small blocks sorted by address after sweep
	- large blocks sorted by size (i.e. best-fit)
	- bitmap to track empty lists
- bitmap sweep automatically coalesces
- sweep reads marks bitmap, doesn't access dead blocks
	(i.e. won't cause swapping)
- bitmap for differentiating pointer/non-pointer blocks
	only pointer blocks are scanned
- bitmaps constitute 3/64 (<5%) space overhead
- no header or trailer on blocks themselves

*/

#include "bmemory.h"
#include "permheap.h"
#include "ostream.h"
#include "fibers.h"
#include "fatal.h"
#include "win.h"
#include <memory.h>
#include <new>
#include <setjmp.h>
#include <stdlib.h>
#include "port.h"
#include "bitmap.h"

#ifdef _MSC_VER
#pragma intrinsic(memset)
#endif

typedef unsigned char byte;

const int GRANULARITY = 8; // must be power of 2
// doubling granularity would halve bitmap sizes and scanning
// but would increase average per block wastage from 4 to 8 bytes

// verify that exits (fatal) ========================================

#define verify(e) \
	if (! (e)) fatal_log("Assertion Failure:\n\n" #e "\n\n(" __FILE__ ")"); else

#define asserteq(e1, e2) \
	if ((e1) != (e2)) fatal_log("Assertion Failure:\n\n" #e1 " != " #e2 "\n\n(" __FILE__ ")"); else

// bitmap ===========================================================

class GcBitmap : public Bitmap
	{
public:
	GcBitmap(int n) : Bitmap(n, mem_committed(Bitmap::required(n)))
		{ }
	};

// pointer bitmap ===================================================

class PtrBitmap : public GcBitmap
	{
public:
	PtrBitmap(void* b, int n) : GcBitmap(n / GRANULARITY), base((char*) b)
		{ }
	void set1(void* p)
		{ Bitmap::set1(xlat(p)); }
	void set1(void* from, void* to)
		{ Bitmap::set1(xlat(from), xlat(to)); }
	void set0(void* p)
		{ Bitmap::set0(xlat(p)); }
	void set0(void* from, void* to)
		{ Bitmap::set0(xlat(from), xlat(to)); }
	int get(void* p)
		{ return Bitmap::get(xlat(p)); }
	void* next1(void* p)
		{ return xlat(Bitmap::next1(xlat(p))); }
	void* next0(void* p)
		{ return xlat(Bitmap::next0(xlat(p))); }
	void* prev1(void* p)
		{ return xlat(Bitmap::prev1(xlat(p))); }
	void set_limit(void* p)
		{ Bitmap::set_limit(xlat(p)); }
	void* get_base()
		{ return base; }
private:
	int xlat(void* p)
		{ return ((char*) p - base) / GRANULARITY; }
	void* xlat(int i)
		{ return base + i * GRANULARITY; }
	char* base;
	};

// blocks ===========================================================

class Blocks
	{
public:
	Blocks(void* base, int n) : bm(base, n)
		{ }
	void clear()
		{ bm.clear(); }
	void create(void* from, void* to)
		{
		bm.set0(from, to);
		bm.set1(from);
		bm.set1(to);
		}
	void chop_up(void* from, void* to)
		{
		bm.set1(from, to);
		}
	// determine begin/end of block from pointer to anywhere in block
	void* from(void* p)
		{ return bm.prev1(p); }
	void* to(void* p)
		{ return bm.next1(p); }

	friend class test_blocks;
private:
	PtrBitmap bm;
	};

// free space =======================================================

class FreeSpace
	{
public:
	FreeSpace() : bm(GCSIZES)
		{
		clear();
		verify(sizeof (FreeBlock) <= GRANULARITY);
		}
	void clear()
		{ 
		memset(lists, 0, sizeof lists);
		bm.clear();
		}
	void add(void* from, void* to);
	void* get(int n); // returns 0 if no block available
	void reverse();
private:
	struct FreeBlock
		{
		FreeBlock(FreeBlock* p, int n) : next(p), size(n)
			{ }
		FreeBlock* next;
		int size;
		};
	FreeBlock* lists[GCSIZES];
	GcBitmap bm;
	};

// same sizes as Doug Lea's malloc
inline int sizeclass(int sz)
	{
	int n = sz >> 9;
	return 
		n == 0 ? (sz >> 3) :
		n <= 4 ? 56 + (sz >> 6) :
		n <= 20 ? 91 + (sz >> 9) :
		n <= 84 ? 110 + (sz >> 12) :
		n <= 340 ? 119 + (sz >> 15) :
		n <= 1364 ? 124 + (sz >> 18) :
		126;
	}

// called by sweep & split in get
void FreeSpace::add(void* from, void* to)
	{
	int sz = (char*) to - (char*) from;
//memset(from, 0, sz);
	int szi = sizeclass(sz);
	// insert in size order (only affects large sizes)
	FreeBlock*& list = lists[szi];
	FreeBlock** prev = &list;
	for (FreeBlock* fb = list; fb && fb->size < sz; prev = &fb->next, fb = fb->next)
		{ }
	*prev = new(from) FreeBlock(*prev, sz);
	bm.set1(szi);
	}

// reverse the small block free lists
// used after sweep to put lists in address order
void FreeSpace::reverse()
	{
	for (int i = 0; i < 64; ++i)
		{
		FreeBlock*& list = lists[i];
		FreeBlock* fb = list;
		list = 0;
		while (fb)
			{
			FreeBlock* next = fb->next;
			fb->next = list;
			list = fb;
			fb = next;
			}
		}
	}

void* FreeSpace::get(int n)
	{
	// use bitmap to skip empty lists
	for (int szi = sizeclass(n) - 1; (szi = bm.next1(szi)) < GCSIZES; )
		{
		FreeBlock*& list = lists[szi];
		FreeBlock** prev = &list;
		for (FreeBlock* fb = list; fb; prev = &fb->next, fb = fb->next)
			{
			if (fb->size >= n)
				{
				// remove from free list
				*prev = fb->next; 
				if (fb->size > n)
					{
					// return remainder to free space
					add((char*) fb + n, (char*) fb + fb->size);
					}
				if (! list)
					bm.set0(szi);
				return fb;
				}
			}
		}
	return 0; // no block available
	}

// MarkStack ========================================================

struct MarkStackOverflow
	{
	};

class MarkStack
	{
public:
	struct Extent
		{
		Extent()
			{ }
		Extent(void* f, void* t) : from(f), to(t)
			{ }
		void* from;
		void* to;
		};
	MarkStack() : sp(stack), end(stack + SIZE)
		{ }
	void push(void* from, void* to)
		{
		if (sp >= end)
			throw MarkStackOverflow();
		*++sp = Extent(from, to); 
		}
	Extent& top()
		{ return *sp; }
	void pop()
		{ --sp; }
	bool empty()
		{ return sp <= stack; }
	void clear()
		{ sp = stack; }
private:
	enum { SIZE = 64000 };
	Extent stack[SIZE];
	Extent* sp;
	Extent* end;
	};

// Final ============================================================

struct Final
	{
	Final(void* o, Final* n) : ob(o), next(n)
		{ }
	void* ob;
	Final* next;
	};

// ==================================================================

static void mark();
static void sweep();

struct MmData // memory manager data
	{
	enum { HEAPSIZE = 64 * 1024 * 1024 }; // 64mb
	MmData() : arena("memory arena", HEAPSIZE), hasptrs(arena.begin(), HEAPSIZE),
		marks(arena.begin(), HEAPSIZE), blocks(arena.begin(), HEAPSIZE),
		final(0), finalqueue(0)
		{ }
	PermanentHeap arena;
	PtrBitmap hasptrs;
	MarkStack markstack;
	PtrBitmap marks;
	Blocks blocks;
	FreeSpace freespace;
	Final* final;
	Final* finalqueue;
	};
static char mm[sizeof (MmData)];
#define arena			((MmData*) mm)->arena
#define hasptrs			((MmData*) mm)->hasptrs
#define markstack		((MmData*) mm)->markstack
#define marks			((MmData*) mm)->marks
#define blocks			((MmData*) mm)->blocks
#define freespace		((MmData*) mm)->freespace
#define final			((MmData*) mm)->final
#define finalqueue		((MmData*) mm)->finalqueue

// allocation =======================================================

inline int roundup(int n)
	{ return ((n - 1) | (GRANULARITY - 1)) + 1; }

const int MIN_INTERVAL = 64 * 1024;
static int alloced = 0;
static int interval = MIN_INTERVAL;

#ifndef __GNUC__
#define __attribute__(stuff)
#endif

void* gc_alloc(int n, bool hp)
	{
	static MmData* notused __attribute__((unused)) = new(mm) MmData;
	static bool exiting = false;

	n = (n == 0 ? GRANULARITY : roundup(n));
	verify(n > 0);
	void* p;
	if (0 != (p = freespace.get(n)))
		goto done;

	if (alloced > interval || arena.remaining() < n)
		{
		garbage_collect();
		if (0 != (p = freespace.get(n)))
			goto done;
		}

	if (arena.remaining() >= n)
		{
		p = arena.alloc(n);
		goto done;
		}

	if (exiting)
		return mem_committed(n); // fall back on os during exit
	exiting = true;
	fatal("out of heap space");

done:
	alloced += n;
	blocks.create(p, (char*) p + n);
	if (hp)
		{
		hasptrs.set1(p);
		memset(p, 0, n);
		}
	else
		hasptrs.set0(p);
	return p;
	}

inline int min(int x, int y)
	{ return x < y ? x : y; }

void* gc_realloc(void* p, size_t n)
	{
	if (n == 0)
		return 0;
	void* q = gc_alloc(n, gc_has_pointers(p));
	if (p)
		memcpy(q, p, min(n, gc_size(p)));
	return q;
	}

int gc_size(void* p)
	{
	verify(arena.contains(p));
	return (char*) blocks.to(p) - (char*) p;
	}

bool gc_inheap(void* p)
	{
	return arena.contains(p);
	}

PermanentHeap& gc_arena()
	{
	return arena;
	}

bool gc_has_pointers(void* p)
	{
	return ! gc_inheap(p) || hasptrs.get(p);
	}

// garbage collect ==================================================

void clear_stack()
	{
	char buf[10000];
	memset(buf, 0, sizeof buf);
	}

bool no_garbage_collection = false;

void garbage_collect()
	{
	alloced = 0;  // prevent nested garbage collect from alloc

	if (no_garbage_collection)
		return ;

	extern void clear_unused();
	clear_unused();

	clear_stack();

	// get registers onto stack
	jmp_buf env;
	memset(&env, 0, sizeof env);
	(void) setjmp(env);

	try
		{
		mark();
		}
	catch (const MarkStackOverflow&)
		{
		return ;
		}

	sweep();

	const int INTERVAL = 4; // same as Boehm's default
	interval = arena.size() / INTERVAL + MIN_INTERVAL;
	}

static void push_static(void* org, void* end)
	{
	verify(org < end);
	verify((reinterpret_cast<long>(org) & 3) == 0); 
	verify((reinterpret_cast<long>(end) & 3) == 0);
	if (&mm + 1 <= org || &mm >= end)
		markstack.push(org, end);
	else // exclude mm
		{
		markstack.push(org, &mm);
		markstack.push(&mm + 1, end);
		}
	}

// for gc_type for debugging
// NOTE: doesn't handle multiple thread stacks
//static void* stack_org = 0; 
//static void* stack_end = 0;

static void push_stack(void* org, void* end)
	{
//stack_org = org; stack_end = end;
	markstack.push(org, end);
	}

static void default_push_roots()
	{
	push_static_roots(push_static);

	Fibers::foreach_stack(push_stack);
	}
static void (*push_roots)() = default_push_roots;

static void mark()
	{
	marks.set_limit(arena.end());
	marks.clear();
	markstack.clear();
	push_roots();
	bool finalized = false;
	for (;;)
		{
		void** pv = (void**) markstack.top().from;
		void** end = (void**) markstack.top().to;
		markstack.pop();
		for (; pv < end; ++pv)
			{
			void* p = *pv;
			if (arena.contains(p) && ! marks.get(p))
				{
				void* from = blocks.from(p);
				void* to = blocks.to(p);
				marks.set1(from, to);
				if (hasptrs.get(from))
					markstack.push(from, to);
				}
			}
		if (markstack.empty())
			{
			// finalization
			if (finalized)
				break ;
			finalized = true;
			Final** prev = &final;
			for (Final* f = final; f; )
				{
				Final* next = f->next;
				if (! marks.get(f->ob))
					{
					// remove from final list
					*prev = f->next;
					// add to finalqueue
					f->next = finalqueue;
					finalqueue = f;
					}
				else
					{
					marks.set1(f, f + 1); // keep Final alive
					prev = &f->next;
					}
				f = next;
				}
			for (Final* q = finalqueue; q; q = q->next)
				{
				marks.set1(q, q + 1); // keep Final alive
				void* from = blocks.from(q->ob);
				void* to = blocks.to(q->ob);
				marks.set1(from, to); // keep object alive while queued
				if (hasptrs.get(from))
					markstack.push(from, to);
				}

			if (markstack.empty())
				break ;
			}
		}
	}

static void sweep()
	{
	freespace.clear();
	void* p = arena.begin();
	if (marks.get(p) == 1)
		p = marks.next0(p);
	for (;;)
		{
		void* from = p;
		p = marks.next1(p);
		if (p >= arena.end())
			{
			arena.free(from);
			break ;
			}
		blocks.chop_up(from, p);
		hasptrs.set0(from, p);
		freespace.add(from, p);
		p = marks.next0(p);
		}
	freespace.reverse();
	}

// stats ============================================================

int gc_arenasize()
	{
	return arena.size();
	}

GcStats* gc_stats()
	{
	static GcStats stats[GCSIZES];
	memset(stats, 0, sizeof stats);
	if (no_garbage_collection)
		return stats;
	for (int i = 0, sz = 0; i < GCSIZES - 1; ++i)
		{
		verify(sizeclass(sz) == i);
		stats[i].minsize = sz;
		if (i < 64)
			sz += 8;
		else if (i < 64 + 32)
			sz += 64;
		else if (i < 64 + 32 + 16)
			sz += 512;
		else if (i < 64 + 32 + 16 + 8)
			sz += 4096;
		else if (i < 64 + 32 + 16 + 8 + 4)
			sz += 32768;
		else if (i < 64 + 32 + 16 + 8 + 4 + 2)
			sz += 262144;
		}
	garbage_collect();
	void* p = arena.begin();
	while (p < arena.end())
		{
		void* from = p;
		if (marks.get(p) == 1) // in use
			{
			p = marks.next0(p);
			for (void* q = from; q < p; )
				{
				void* from = q;
				q = blocks.to(q);
				int sz = (char*) q - (char*) from;
				int szi = sizeclass(sz);
				if (hasptrs.get(from))
					{
					++stats[szi].ptr_count;
					stats[szi].ptr_size += sz;
					}
				else
					{
					++stats[szi].nonptr_count;
					stats[szi].nonptr_size += sz;
					}
				}
			}
		else // free
			{
			p = marks.next1(p);
			int sz = (char*) p - (char*) from;
			int szi = sizeclass(sz);
			++stats[szi].free_count;
			stats[szi].free_size += sz;
			}
		}
	return stats;
	}

#define K(n)	((n) / 1024) << " k"

Ostream& operator <<(Ostream& os, GcStats* stats)
	{
	os << setw(10) << "minsize" <<
		setw(18) << right << "free" <<
		setw(18) << right << "ptr" <<
		setw(18) << right << "nonptr" <<
		endl << endl;
	GcStats totals = { 0 };
	for (int i = 0; i < GCSIZES; ++i)
		if (stats[i].free_count + stats[i].ptr_count + stats[i].nonptr_count > 0)
			{
			os << setw(10) << stats[i].minsize <<
				setw(8) << stats[i].free_count << setw(8) << K(stats[i].free_size) <<
				setw(8) << stats[i].ptr_count << setw(8) << K(stats[i].ptr_size) <<
				setw(8) << stats[i].nonptr_count << setw(8) << K(stats[i].nonptr_size) <<
				endl;
			totals.free_count += stats[i].free_count;
			totals.free_size += stats[i].free_size;
			totals.ptr_count += stats[i].ptr_count;
			totals.ptr_size += stats[i].ptr_size;
			totals.nonptr_count += stats[i].nonptr_count;
			totals.nonptr_size += stats[i].nonptr_size;
			}
	os << endl;
	os << setw(10) << "" <<
		setw(8) << totals.free_count << setw(8) << K(totals.free_size) <<
		setw(8) << totals.ptr_count << setw(8) << K(totals.ptr_size) <<
		setw(8) << totals.nonptr_count << setw(8) << K(totals.nonptr_size) <<
		setw(8) << totals.ptr_count + totals.nonptr_count << 
		setw(8) << K(totals.ptr_size + totals.nonptr_size) <<
		endl;
	os << endl;
	os << "arena: " << K(arena.size()) << endl;

	int n = 0;
	for (Final* f = final; f; f = f->next, ++n)
		{ }
	os << "final: " << n << endl;

	return os;
	}

// finalize =========================================================

void finalize(void* ob)
	{
	final = new(gc_alloc(sizeof (Final), false)) Final(ob, final);
	}

void* nextfinal()
	{
	if (! finalqueue)
		return 0;
	void* p = finalqueue->ob;
	Final* next = finalqueue->next;
	finalqueue = next;
	return p;
	}

void removefinal(void* p)
	{
	Final** prev = &final;
	for (Final* f = final; f; prev = &f->next, f = f->next)
		if (f->ob == p)
			{
			*prev = f->next; // remove it from list
			break ;
			}
	}

Final* getfinal()
	{
	return final;
	}

#if defined(_MSC_VER)
struct Region
	{
	void* start;
	void* end;
	};
	
Region get_static_region()
	{
	char exefile[512];
	GetModuleFileName(NULL, exefile, sizeof (exefile));

	HANDLE hFile = CreateFile(exefile, GENERIC_READ, FILE_SHARE_READ, NULL,
						OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
	if ( hFile == INVALID_HANDLE_VALUE )
		fatal_log("get_static_region: unable to open exe");

	HANDLE hFileMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
	if ( hFileMapping == 0 )
		fatal_log("get_static_region: unable to create mappping of exe");

	void* lpFileBase = MapViewOfFile(hFileMapping, FILE_MAP_READ, 0, 0, 0);
	if ( lpFileBase == 0 )
		fatal_log("get_static_region: unable to map view of exe");

	IMAGE_DOS_HEADER* dosHeader = (PIMAGE_DOS_HEADER)lpFileBase;
	if ( dosHeader->e_magic != IMAGE_DOS_SIGNATURE )
		fatal_log("get_static_region: bad magic");

	IMAGE_NT_HEADERS* pNTHeader = (PIMAGE_NT_HEADERS)( (DWORD) dosHeader + dosHeader->e_lfanew );
	if ( IsBadReadPtr(pNTHeader, sizeof(IMAGE_NT_HEADERS)) ||
	     pNTHeader->Signature != IMAGE_NT_SIGNATURE )
		fatal_log("get_static_region: unknown exe type");
	
	Region region;
	region.start = 0;
	IMAGE_SECTION_HEADER* section = (IMAGE_SECTION_HEADER*)(pNTHeader+1);
	for (int i = 0; i < pNTHeader->FileHeader.NumberOfSections; ++i, ++section)
		if (0 == strcmp((char*) section->Name, ".data"))
			{
			region.start = (void*) (0x400000 + section->VirtualAddress);
			region.end = (void*) ((char*) region.start + section->Misc.VirtualSize);
			break ;
			}
	if (! region.start)
		fatal_log("get_static_region: couldn't find .data section");

	UnmapViewOfFile(lpFileBase);
	CloseHandle(hFileMapping);
	CloseHandle(hFile);
	
	return region;
	}

void push_static_roots(void (*push)(void*, void*))
	{
	static Region region = get_static_region(); // only done once
		
	for (void* p = region.start; p < region.end; )
		{
		MEMORY_BASIC_INFORMATION m;
		VirtualQuery(p, &m, sizeof(m));
		void* end = (char *)p + m.RegionSize;
		if (m.State == MEM_COMMIT &&
			(m.Protect == PAGE_READWRITE || m.Protect == PAGE_EXECUTE_READWRITE ||
			m.Protect == PAGE_WRITECOPY || m.Protect == PAGE_EXECUTE_WRITECOPY))
			push(p, end);
		p = (char*) end;
		}
	}
#elif defined(__GNUC__)
extern "C" int _data_start__[];
extern "C" int _data_end__[];
extern "C" int _bss_start__[];
extern "C" int _bss_end__[];

void push_static_roots(void (*push)(void*, void*))
	{
	push(_data_start__, _data_end__);
	push(_bss_start__, _bss_end__);
	}
#endif	
	
// tests ============================================================

#undef verify
#undef asserteq

#include "testing.h"

#include "random.h"

inline void swap(int& x, int& y)
	{ int tmp = x; x = y; y = tmp; }

class test_ptrbitmap : public Tests
	{
	TEST(0, main)
		{
		const int N = 1024;
		struct G { char s[GRANULARITY]; };
		G* B = (G*) 0x10000000;
		PtrBitmap bm(B, N * GRANULARITY);
		bm.clear();
		int i;
		for (i = 0; i < N; ++i)
			verify(bm.get(B + i) == 0);
		srand(1);
		for (i = 0; i < N / 2; ++i)
			bm.set1(B + random(N));
		srand(1);
		for (i = 0; i < N / 2; ++i)
			verify(bm.get(B + random(N)) == 1);
		}
	};
REGISTER(test_ptrbitmap);

class test_blocks : public Tests
	{
	TEST(0, main)
		{
		const int N = 1024;
		struct G { char s[GRANULARITY]; };
		G* B = (G*) 0x10000000;
		Blocks bm(B, N * GRANULARITY);
		int i;
		for (i = 0; i < N / 2; ++i)
			{
			G* from = B + random(N - 31);
			G* to = from + random(31);
			G* g;
			bm.create(from, to);
			verify(bm.bm.get(from) == 1);
			for (g = from + 1; g < to; ++g)
				verify(bm.bm.get(g) == 0);
			verify(bm.bm.get(to) == 1);
			for (g = from; g < to; ++g)
				{
				asserteq(bm.from(g), from);
				asserteq(bm.to(g), to);
				}
			}
		}
	};
REGISTER(test_blocks);

#ifdef TESTING

bool is_client = false;
char* session_id = "";

void message(const char* s, const char* t)
	{
	MessageBox(0, t, s, MB_OK | MB_TASKMODAL | MB_TOPMOST | MB_SETFOREGROUND);
	}

void clear_unused()
	{
	}

void Fibers::foreach_proc(ProcFn fn)
	{
	}

void Fibers::foreach_stack(StackFn fn)
	{
	int junk;
	void* p;
#if defined(_MSC_VER)
	_asm
		{
		mov eax,fs:4
		mov p,eax
		}
#elif defined(__GNUC__)
	asm("movl %%fs:0x4,%%eax" : "=a" (p));
#else
#warning "replacement for inline assembler required"
#endif

	fn(&junk, p);
	}
	
class test_freespace : public Tests
	{
	TEST(0, sizeclass)
		{
		verify(sizeclass(0) == 0);
		verify(sizeclass(1) == 0);
		verify(sizeclass(7) == 0);
		verify(sizeclass(8) == 1);
		verify(sizeclass(12) == 1);
		verify(sizeclass(16) == 2);
		verify(sizeclass(512) == 64);
		}
	TEST(1, main)
		{
		gc_alloc(1); // to initialize

		void* p;
		void* q;

		p = arena.alloc(8);
		freespace.add(p, (char*) p + 8);
		q = freespace.get(8);
		verify(q == p);

		p = arena.alloc(32);
		freespace.add(p, (char*) p + 32);
		q = freespace.get(16);
		verify(q == p);
		q = freespace.get(8);
		verify(q == (char*) p + 16);
		q = freespace.get(8);
		verify(q == (char*) p + 24);

		arena.free(arena.begin()); // free all
		freespace.clear();
		}
	};
REGISTER(test_freespace);

struct PushRoots
	{
	PushRoots(void (*fn)()) : prevfn(push_roots)
		{ push_roots = fn; }
	~PushRoots()
		{ push_roots = prevfn; }
	void (*prevfn)();
	};

static void* p;
static void push_roots_p()
	{
	markstack.push(&p, &p + 1);
	}

class test_bmemory1 : public Tests
	{
	TEST(0, simple)
		{
		PushRoots tmp(push_roots_p);

		p = gc_alloc(23);
		verify(p == arena.begin());
		garbage_collect();
		p = gc_alloc(23);			// first alloc should now be dead
		verify(p == (char*) arena.begin() + 24);
		garbage_collect();
		p = gc_alloc(5);
		verify(p == arena.begin());
		p = gc_alloc(3);
		verify(p == (char*) arena.begin() + 8);
		p = gc_alloc(8);
		verify(p == (char*) arena.begin() + 16);
		p = gc_alloc(50);
		verify(p == (char*) arena.begin() + 48);
		p = 0;
		garbage_collect();
		p = gc_alloc(500);			// sweep should return space to arena
		verify(p == arena.begin());
		p = 0;
		}
	};
REGISTER(test_bmemory1);

int final_count = 0;
struct TestFinal
	{
	TestFinal()
		{ ++final_count; }
	~TestFinal()
		{ --final_count; }
	};
class test_final : public Tests
	{
	TEST(0, main)
		{
		PushRoots tmp(push_roots_p);

		verify(final_count == 0);
		TestFinal* ob = new(gc_alloc(sizeof (TestFinal))) TestFinal;
		p = ob; // ob isnt visible to garbage collect
		verify(final_count == 1);
		finalize(ob);
		garbage_collect();
		verify(final->ob == ob);
		verify(nextfinal() == 0);
		p = 0; // now dead
		garbage_collect();
		verify(final == 0);
		verify(nextfinal() == ob);
		verify(nextfinal() == 0);
		ob->~TestFinal();
		verify(final_count == 0);
		}
	};
REGISTER(test_final);

class test_bmemory2 : public Tests
	{
	TEST(1, random)
		{
		struct Data
			{
			int x;
			int* p;
			};
		const int NDATA = 4091;
		static Data* data[NDATA];

		memset(data, 0, sizeof (data));
		for (int i = 0; i < 1000000; ++i)
			{
			int j = random(NDATA);
			if (data[j])
				{
				verify(data[j]->x == j);
				verify(*data[j]->p == j * NDATA);
				}
			data[j] = (Data*) gc_alloc(random(61));
			data[j]->x = j;
			data[j]->p = (int*) gc_alloc(random(1021), false);
			data[j]->p[0] = j * NDATA;

			verify(data[j]->x == j);
			verify(data[j]->p[0] == j * NDATA);
			}
		// dump_stats();
		memset(data, 0, sizeof (data));
		garbage_collect();
		// dump_stats();
		}
	};
REGISTER(test_bmemory2);

#endif
